import math
from functools import lru_cache

# 使用lru_cache缓存已计算过的素数结果，避免重复计算
@lru_cache(maxsize=None)
def is_prime(n):
    # 处理边界情况
    if n <= 1:
        return False
    if n <= 3:
        return True
    # 排除能被2或3整除的数
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    # 小素数快速检查 - 对于大数，可以先检查是否能被几个小素数整除
    small_primes = [5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for prime in small_primes:
        if prime * prime > n:
            break
        if n % prime == 0:
            return False
    
    # 使用6k±1优化 - 除了2和3，所有素数都可以表示为6k±1的形式
    sqrt_n = int(math.isqrt(n))  # Python 3.8+ 提供的更高效平方根函数
    i = 5  # 从5开始，按照6k±1的形式检查
    while i <= sqrt_n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6  # 跳到下一个6k-1的位置
    
    return True

# 检查是否为回文数
def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

# 生成指定长度的回文数列表，利用回文数特性进行优化
def generate_palindromes(length):
    palindromes = []
    
    # 1位数回文数
    if length == 1:
        return list(range(1, 10))
    
    # 偶数位数回文数 - 除了11外，所有偶数位回文数都能被11整除
    if length % 2 == 0:
        return [11] if length == 2 else []
    
    # 奇数位数回文数
    half = length // 2
    start = 10 ** half
    end = 10 ** (half + 1)
    
    # 对于大数，使用更高效的回文数生成方法
    for i in range(start, end):
        s = str(i)
        # 生成回文数：前半部分 + 后半部分的反转（去掉最后一位）
        palindrome = int(s + s[:-1][::-1])
        palindromes.append(palindrome)
    
    return palindromes

# 查找回文素数的主函数
def find_palindrome_primes(max_limit=10**9):
    palindrome_primes = []
    
    # 优化点1：提前处理特殊情况
    if max_limit < 2:
        return []
    
    # 优化点2：分离处理1位数回文素数
    if max_limit >= 2:
        # 1位数的回文素数就是所有1位数素数
        for num in range(2, min(10, max_limit + 1)):
            if is_prime(num):  # 只添加素数
                palindrome_primes.append(num)
    
    # 优化点3：单独处理唯一的2位数回文素数11
    if max_limit >= 11:
        palindrome_primes.append(11)
    
    # 优化点4：从3位数开始，只生成奇数位数的回文数
    # 因为除了11外，所有偶数位回文数都能被11整除，不是素数
    length = 3
    max_length = len(str(max_limit))
    
    # 优化点5：使用生成器逐步处理，减少内存占用
    while length <= max_length:
        # 生成当前长度的所有回文数
        current_pals = generate_palindromes(length)
        
        # 检查每个回文数是否为素数且不超过max_limit
        for pal in current_pals:
            if pal > max_limit:
                break  # 因为生成的回文数是递增的，后面的数会更大，直接break
            if is_prime(pal):
                palindrome_primes.append(pal)
        
        length += 2  # 只考虑奇数位数的回文数
    
    return palindrome_primes

if __name__ == "__main__":
    import time
    start_time = time.time()
    
    # 查找10位数以内的所有回文素数（最大1e9）
    primes = find_palindrome_primes(10**9)
    
    end_time = time.time()
    
    print(f"回文素数数量: {len(primes)}")
    print(f"查找用时: {end_time - start_time:.4f} 秒")
    
    # 输出前10个回文素数
    print("前10个回文素数:", primes[:10])
    
    # 输出后10个回文素数
    print("后10个回文素数:", primes[-10:])